import java.util.Arrays;

public class Binary_search {

    //绝对正确的方法
    public static boolean right(int[] arr,int num) {
        for(int i=0; i<arr.length; ++i) {
            if(arr[i] == num) {
                return true;
            }
        }
        return false;
    }


    //在有序数组中查找num是否存在
    public static boolean exist(int[] arr,int num) {
        if(arr==null || arr.length==0) {
            return false;
        }
        int L=0,R=arr.length-1,mid=0;
        while(L<=R) {
            mid = L + ((R-L)>>1);
            if(arr[mid] == num) {
                return true;
            }
            else if(arr[mid] > num) {
                R=mid-1;
            }
            else {
                L=mid+1;
            }
        }
        return false;
    }

    //在有序数组中找>=num最左的位置
    public static int findLeft(int[] arr,int num) {
        if(arr==null || arr.length==0) {
            return -1;
        }
        int L=0,R=arr.length-1,mid=0,ret=-1;
        while(L<=R) {
            mid = L + ((R-L)>>1);
            if(arr[mid] >= num) {
                ret = mid;
                R=mid-1;
            }
            else {
                L=mid+1;
            }
        }
        return ret;
    }

    //在有序数组中找<=num最右的位置
    public static int findRight(int[] arr,int num) {
        if(arr==null || arr.length==0) {
            return -1;
        }
        int L=0,R=arr.length-1,mid=0,ret=-1;
        while(L<=R) {
            mid = L + ((R-L)>>1);
            if(arr[mid] <= num) {
                ret = mid;
                L=mid+1;
            }
            else {
                R=mid-1;
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        System.out.println("测试开始");
        //数组的长度
        int N=15;
        //数组每个值的取值范围1-1000
        int V=1000;
        //测试的次数
        int sizeTime=1000;
        for(int i=0; i<sizeTime; ++i) {
            int[] arr=randomArr(N,V);
            Arrays.sort(arr);
            int num=(int) (Math.random()*V) + 1;
            if(right(arr,num) != exist(arr,num)) {
                System.out.println("出错了");
                System.out.println(Arrays.toString(arr));
                System.out.println(num);

            }
        }
        System.out.println("测试结束");
    }

    public static int[] randomArr(int N,int V) {
        int [] arr=new int[N];
        for(int i=0; i<N; ++i) {
            arr[i] = (int) (Math.random()*V) + 1;  //生成随机数[1,V]
        }
        return arr;
    }
}
